#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include "./getch/getch.h"

#define MAXWORD 100
#define YES	1
#define NO	0

struct tnode 		// the tree node:
{
	char *word;	// points to the test
	int match;	// match founf
	struct tnode *left;	// left child
	struct tnode *right;	// right child
};

struct tnode *addtreex(struct tnode *, char *, int, int *);
void treeprint(struct tnode *);

// print in alphabetic order each group of variable names
// identical in the first num characters(default 6) 
int main(int argc, char const *argv[])
{
	struct tnode *root;
	char word[MAXWORD];
	int found = NO;		// YES if match was found
	unsigned int num;	// number of the first ident chars

	num = (--argc && (*++argv)[0] == '-') ? atoi(argv[0] + 1) : 6;
	printf("%d\n", num);
	root = NULL;
	while(getword(word, MAXWORD) != EOF)
	{
		if(isalpha(word[0]) && strlen(word) >= num)
			root = addtreex(root, word, num, &found);
		found = NO;
	}
	treeprint(root);
	return 0;
}

struct tnode *talloc(void);
/**
 *	strdup 不在标准中，但很多编译器会支持
 *	因此如果不使用 string.h 中的 strdup, 就要在程序中自己声明和定义 strdup, gcc编译时要加上 -ansi  -pedantic 参数
 *	如果使用 string.h 中的 strdup, 就不能在程序中自己声明和定义 strdup, 编译时不带 -ansi -pedantic, 采用默认编译参数
**/
char *mystrdup(char *);
int compare(char *, struct tnode *, int, int *);

// addtree: add a node with w, at or below p
struct tnode *addtreex(struct tnode *p, char *w, int num, int *found)
{
	int cond;

	if(p == NULL)		// a new word has arrived
	{
		p = talloc();	// make a new node
		p->word = mystrdup(w);
		p->match = *found;
		p->left = p->right = NULL;
	}
	else if((cond = compare(w, p, num, found)) < 0)
		p->left = addtreex(p->left, w, num, found);	
	else if(cond >  0)	
		p->right = addtreex(p->right, w, num, found);

	return p;
}

// compare: compare words and update p->match
int compare(char *s, struct tnode *p, int num, int *found)
{
	int i;
	char *t = p->word;

	for(i = 0; *s == *t; i++, s++, t++)
	{
		if(*s == '\0')
			return 0;
	}
	if(i >= num)
	{
		*found = YES;
		p->match = YES;
	}
	return *s - *t;
}

// treeprint: in-order print of tree p
void treeprint(struct tnode *p)
{
	if(p != NULL)
	{
		treeprint(p->left);
		printf("%4d : %s\n", p->match, p->word);
		if(p->match)
			printf("%s\n", p->word);
		treeprint(p->right);
	}
}

// talloc: make a tnode
struct tnode *talloc(void)
{
	return (struct tnode *)malloc(sizeof(struct tnode));   
}

char *mystrdup(char *s)		// make a duplicate of s
{
	char *p;

	p = (char *)malloc(strlen(s) + 1);		// +1 for '\0'
	if(p != NULL)
		strcpy(p, s);
	return p;
}

/**
 * $ gcc -W -Wall -ansi -pedantic 6-2.c -o 6-2
 *
 * $ ./6-2.exe < 6-2.c
 *
**/
